// nc40 链表相加(二)
// https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
// 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
// 给定两个这种链表，请生成代表两个整数相加值的结果链表。
// 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

#include <deque>
#include <iostream>
using namespace std;

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
 public:
  /**
   *
   * @param head1 ListNode类
   * @param head2 ListNode类
   * @return ListNode类
   */
  //   9 9 9
  // 9 9 9 9
  // -------
  ListNode* nodeAdd(ListNode* t1, ListNode* t2, int carry) {
    if (t1 && t2) {
      t1->val += (t2->val + carry);
      return t1;
    }
    if (t1) {
      t1->val += carry;
      return t1;
    }
    if (t2) {
      t2->val += carry;
      return t2;
    }
    return nullptr;
  }
  ListNode* addInList(ListNode* head1, ListNode* head2) {
    // write code here
    if (head1 == nullptr) {
      return head2;
    }
    if (head2 == nullptr) {
      return head1;
    }
    deque<ListNode*> dqNode1;
    deque<ListNode*> dqNode2;
    ListNode* p = head1;
    while (p) {
      dqNode1.push_back(p);
      p = p->next;
    }
    p = head2;
    while (p) {
      dqNode2.push_back(p);
      p = p->next;
    }
    int carry = 0;
    ListNode* newHead = new ListNode(0);
    ListNode* curHead = newHead->next;  // is null
    while (true) {
      ListNode* t1 = nullptr;
      if (!dqNode1.empty()) {
        t1 = dqNode1.back();
        dqNode1.pop_back();
      }
      ListNode* t2 = nullptr;
      if (!dqNode2.empty()) {
        t2 = dqNode2.back();
        dqNode2.pop_back();
      }
      ListNode* t3 = nodeAdd(t1, t2, carry);
      if (t3 == nullptr) {
        break;
      }
      if (t3->val >= 10) {
        t3->val -= 10;
        carry = 1;
      } else {
        carry = 0;
      }
      t3->next = curHead;
      curHead = t3;
    }
    if (carry > 0) {
      ListNode* t3 = new ListNode(carry);
      t3->next = curHead;
      curHead = t3;
    }
    printf("ss");
    return curHead;
  }
};

int main_nc40() {
  Solution sol;
  return 0;
}
